class Solution {
    public int check(int[] position, long x) {
        int pre = position[0];
        int count = 1;
        for (int i = 1; i < position.length; i++) {
            int index = position[i] - pre;
            if (index >= x) {
                pre = position[i];
                count++;
            }
        }
        return count;
    }

    public int maxDistance(int[] position, int m) {
        Arrays.sort(position);
        long l = 1;
        long r = (int)1e9;
        long res = 0;
        while (l <= r) {
            long mid = (l + r) >> 1;
            if (check(position, mid) >= m) {
                res = mid;
                l = mid + 1;
            }
            else {
                r = mid - 1;
            }
        }
        return (int)res;
    }
}
